package com.zs.letcode.tencent;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * 括号生成
 * 数字 n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：["()"]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 8
 * 相关标签
 * 字符串
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/tencent/x5ku2e/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/7/23 08:17
 */
public class Chapter41 {
    public static void main(String[] args) {

    }

    private class Solution {
        /**
         * 【最简单易懂的】动态规划
         */
        public List<String> generateParenthesis(int n) {
            List<List<String>> total = new ArrayList<>();
            if (n == 0) {
                return new ArrayList<>();
            }
            total.add(Arrays.asList("()"));
            for (int i = 2; i < n + 1; i++) {
                List<String> temp = new ArrayList<>();
                for (int j = 0; j < i; j++) {
                    List<String> list1 = total.get(j);
                    List<String> list2 = total.get(i - 1 - j);
                    for (String k1 : list1) {
                        for (String k2 : list2) {
                            if (Objects.isNull(k1)) {
                                k1 = "";
                            }
                            if (Objects.isNull(k2)) {
                                k2 = "";
                            }
                            String el = "(" + k1 + ")" + k2;
                            temp.add(el);
                        }
                    }
                }
                total.add(temp);
            }
            return total.get(n);
        }

        /**
         * 方法一：暴力法
         */
        public List<String> generateParenthesis1(int n) {
            List<String> combinations = new ArrayList<>();
            generateAll(new char[2 * n], 0, combinations);
            return combinations;
        }

        private void generateAll(char[] current, int pos, List<String> result) {
            if (pos == current.length) {
                if (valid(current)) {
                    result.add(new String(current));
                }
            } else {
                current[pos] = '(';
                generateAll(current, pos + 1, result);
                current[pos] = ')';
                generateAll(current, pos + 1, result);
            }
        }

        private boolean valid(char[] current) {
            int balance = 0;
            for (char c : current) {
                if (c == '(') {
                    balance++;
                } else {
                    balance--;
                }
                if (balance < 0) {
                    return false;
                }
            }
            return balance == 0;
        }

        /**
         * 方法二：回溯法
         */
        public List<String> generateParenthesis2(int n) {
            List<String> ans = new ArrayList<>();
            backtrack(ans, new StringBuffer(), 0, 0, n);
            return ans;
        }

        private void backtrack(List<String> ans, StringBuffer cur, int open, int close, int max) {
            if (cur.length() == max * 2) {
                ans.add(cur.toString());
                return;
            }
            if (open < max) {
                cur.append('(');
                backtrack(ans, cur, open + 1, close, max);
            }
            if (close < open) {
                cur.append(')');
                backtrack(ans, cur, open, close + 1, max);
                cur.deleteCharAt(cur.length() - 1);
            }
        }

        /**
         * 方法三：按括号序列的长度递归
         */
        List[] cache = new ArrayList[100];

        public List<String> generateParenthesis3(int n) {
            return generate(n);
        }

        private List<String> generate(int n) {
            if (cache[n] != null) {
                return cache[n];
            }
            List<String> ans = new ArrayList<>();
            if (n == 0) {
                ans.add("");
            } else {
                for (int c = 0; c < n; c++) {
                    for (String left : generate(c)) {
                        for (String right : generate(n - 1 - c)) {
                            ans.add("(" + left + ")" + right);
                        }
                    }
                }
            }
            cache[n] = ans;
            return ans  ;
        }
    }
}
